from tools_algorithm import *


class Solution:
    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
        n = len(nums)

        @cache
        def f(limit, id, s):
            if id > numSlots:
                return -inf
            if limit == 0:
                return 0
            ans = f(limit, id + 1, 0)
            if s < 2:
                for i in range(n):
                    if limit >> i & 1 == 1:
                        ans = max(ans, f(limit ^ (1 << i), id, s + 1) + (nums[i] & id))
            return ans

        return f((1 << n) - 1, 1, 0)


class Solution:
    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
        n = len(nums)

        b = [1]
        for _ in range(10):
            b.append(b[-1] * 3)

        @cache
        def f(limit, id):
            if id == n:
                return 0
            ans = f(limit, id + 1)
            t, i = limit, 1
            while t > 0:
                t, m = divmod(t, 3)
                if m > 0:
                    ans = max(ans, f(limit - b[i - 1], id + 1) + (i & nums[id]))
                i += 1
            return ans

        return f(b[numSlots] - 1, 0)


s = Solution()
print(s.maximumANDSum(nums=[1, 2, 3, 4, 5, 6], numSlots=3))
